package DP.Medium;

import java.util.Arrays;

public class LC0322 {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; // 为了凑到amount，最少需要的硬币数
        // base case: amount=0时，硬币数为0；amount小于最小的硬币面额时，应返回-1
        Arrays.fill(dp, -1);
        dp[0] = 0;

        int minCoinValue = coins[0];
        for (int i = 1; i < coins.length; i++) {
            minCoinValue = Math.min(minCoinValue, coins[i]);
        }

        for (int i = minCoinValue; i <= amount; i++) { // amount大于0但小于coins[0]时，一定没有合理的方法
            int minNumCoins = amount + 1;
            for (int coin : coins) {
                if (i - coin < 0 || dp[i - coin] == -1) continue;
                minNumCoins = Math.min(minNumCoins, 1 + dp[i - coin]);
            }
            if (minNumCoins != amount + 1) dp[i] = minNumCoins;
        }

        return dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = new int[]{474, 83, 404, 3};
        int amount = 264;
        LC0322 solver = new LC0322();
        System.out.println(solver.coinChange(coins, amount));
    }
}
